class BitBree:
    def __init__(self, node):
        self.data = node
        self.rchild = None
        self.lchild = None
        self.parent = None

class BST:
    def __init__(self, lis):
        self.root = None
        if lis:
            for ii in lis:
                self.insert_no(ii)
    
    def insert_no(self, val):
        p = self.root
        if not self.root:
            self.root = BitBree(val)
        while True:
            if val > p.data:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BitBree(val)
                    p.lchild.parent = p
                    return

            elif val < p.data:
                if p.lchild:
                    p = p.lchild
                else:
                    p.lchild = BitBree(val)
                    p.lchild.parent = p
                    return
            else:
                return p
        
    def insert(self, node, val):
        if not node:
            node = BitBree(val)
            return node
        elif val < node.data:
            node.lchild = self.insert(node.lchild, val)
        elif val > node.data:
            node.rchild = self.insert(node.rchild, val)
        else:
            return 
    
    def search(self, val):
        node = BitBree(val)
        p = self.root
        while p:
            if node.data > p.data:
                p = p.rchild
            elif node.data < p.data:
                p = p.lchild
            else:
                return p
        return None
    

    def delete_mode_1(self, node):
        if not node.parent:
            self.root = None
        
        if node == node.parent.lchild:
            node.parent.lchild = None
        else:
            node.parent.rchild = None
    
    def delete_mode_21(self, node):
        # 一个左孩子
        p = self.root
        if not node.parent:
            p = p.lchild
            p.parent = None
        if node == node.parent.lchild:
            node.parent.lchild = node.lchild
            node.lchild.parent = node.parent
        
        else:
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent


    def delete_mode_22(self, node):
        p = self.root
        if not node.parent:
            p = p.rchild
            p.parent = None
        if node == node.parent.lchild:
            node.parent.lchild =node.rchild
            node.rchild.parent = node.parent

        else:
            node.parent.rchild = node.rchild
            node.rchild.parent = node.parent
        
    def delete(self, val):
        node = self.search(val)
        if not node.lchild and not node.lchild:
            self.delete_mode_1(node)
        
        elif not node.rchild:
            self.delete_mode_21(node)
        elif not node.lchild:
            self.delete_mode_22(node)
        else:
            min_node = node.rchild
            while min_node.lchild:
                min_node = min_node.lchild
            node.data = min_node.data
            if min_node.rchild:
                self.delete_mode_22(min_node)
            else:
                self.delete_mode_1(min_node)
            

        
        








